package mashibing.class22;

/**
 * arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * 每个值都认为是一种面值，且认为张数是无限的。
 * 返回组成aim的最少货币数
 */
public class Class22_2_MinCoinsNoLimit {

    public static int minCoins1(int[] arr, int aim) {
        return process(arr, 0, aim);
    }

    private static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return rest == 0 ? 0 : Integer.MAX_VALUE;
        } else {
            int min = Integer.MAX_VALUE;
            for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                int next = process(arr, index + 1, rest - zhang * arr[index]);
                if (next != Integer.MAX_VALUE) {
                    min = Math.min(min, next + zhang);
                }
            }
            return min;
        }
    }

    public static int minCoins2(int[] arr, int aim) {
        int[][] dp = new int[arr.length + 1][aim + 1];
        dp[arr.length][0] = 0;
        for (int i = 1; i <= aim; i++) {
            dp[arr.length][i] = Integer.MAX_VALUE;
        }
        for (int index = arr.length - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int min = Integer.MAX_VALUE;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                    int next = dp[index + 1][rest - zhang * arr[index]];
                    if (next != Integer.MAX_VALUE) {
                        min = Math.min(min, next + zhang);
                    }
                }
                dp[index][rest] = min;
            }
        }
        return dp[0][aim];
    }

    public static int minCoins3(int[] arr, int aim) {
        int[][] dp = new int[arr.length + 1][aim + 1];
        dp[arr.length][0] = 0;
        for (int i = 1; i <= aim; i++) {
            dp[arr.length][i] = Integer.MAX_VALUE;
        }
        for (int index = arr.length - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int min = dp[index + 1][rest];
                if (rest - arr[index] >= 0 && dp[index][rest - arr[index]] != Integer.MAX_VALUE) {
                    min = Math.min(min, dp[index][rest - arr[index]] + 1);
                }
                dp[index][rest] = min;
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int[] arr = {27, 14, 2, 9, 30, 21, 19, 26, 20};
        int aim = 15;
        System.out.println(minCoins1(arr, aim));     // 4
        System.out.println(minCoins2(arr, aim));     // 4
        System.out.println(minCoins3(arr, aim));     // 4
    }
}
